package chapter03_binaryTree;

import jdk.nashorn.internal.objects.NativeUint8Array;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * 描述：
 *      判断是否是一个搜索二叉树或者完全二叉树
 * @author hl
 * @date 2021/5/30 10:22
 */
public class IsBSTOrCBT {
    /**
     * 判断二叉树是否是一颗搜索二叉树
     * @param head
     * @return
     */

    /**
     * morris中序遍历
     * @param head
     * @return
     */
    public boolean isBST(Node head){
        if (head == null) {
            return true;
        }
        Node cur = head, cur1 = null, pre =  null;
        boolean flag = true;
        while(cur != null){
            if (cur.left != null) {
                cur1 = cur.left;
                while(cur1.right != null && cur1.right != cur){
                    cur1 = cur1.right;
                }
                if (cur1.right == null) {
                    cur1.right = cur;
                    cur = cur.left;
                    continue;
                }else{
                    cur1.right = null;
                }
            }
            if(pre != null && pre.val > cur.val){
                flag = false;
            }
            pre = cur;
            cur = cur.right;
        }
        return flag;
    }

    /**
     * 普通遍历
     * @param head
     * @return
     */
    public boolean isBST2(Node head){
        if (head == null) {
            return true;
        }
        boolean l = isBST2(head.left);
        boolean r = isBST2(head.right);
        if (!l || !r || head.left.val > head.val || head.right.val < head.val) {
            return false;
        }
        return true;
    }


    /**
     * 判断二叉树是否是一颗完全二叉树
     * 完全二叉树：由满二叉树引申出来的结构，除了最后一层意外，其余各层的结点数达到最大，最后一层的结点必须从左到有连续
     * 层序遍历，当发现某个结点的孩子结点为空，此刻开始后序所有结点的孩子都应该为空
     * @param head
     * @return
     */
    public boolean isCBT(Node head){
        if (head == null) {
            return true;
        }
        Deque<Node> queue = new LinkedList<>();
        queue.offer(head);
        //判断开启的标识，当某个结点的孩子结点为空时，开启标识
        boolean leaf = false;
        Node l = null;
        Node r = null;
        while(!queue.isEmpty()){
            head = queue.poll();
            if ((leaf && (l != null || r != null)) || (l == null && r != null)) {
                //直接针对一个结点进行判断
                return false;
            }
            if (l != null) {
                queue.offer(l);
            }
            if (r != null) {
                queue.offer(r);
            }else{
                leaf = true;
            }
        }
        return true;
    }

}
